#include <iostream>
#include <vector>
#include <utility>
#include <limits.h>

using namespace std;

typedef struct BSTreeNode {
	int value;
	struct BSTreeNode * left;
	struct BSTreeNode * right;
} BSTreeNode;

#define max(a,b) (a>b)?(a):(b)

/**
 * given a tree rooted at root, calculate its height and max distance among nodes in this tree.
 * they are integrated into a pair as <height, max distance>
 */
pair<int,int> max_distance (BSTreeNode * root) {
	if (root->left == NULL && root->right == NULL)
		return make_pair(0,0);
	
	pair<int,int> pl, pr;
	int longer = INT_MIN;
	int m = 0;

	if (root->left != NULL) {
		pl = max_distance (root->left);
		m += pl.first + 1;
	}

	if (root->right != NULL) {
		pr = max_distance (root->right);
		m += pr.first + 1;
	}

	longer = max(pl.second, pr.second);
	m = max(m,longer);

	return make_pair(max(pl.first, pr.first) + 1, m);
}


int main()
{
	/*
	 *	Testing Tree:
	 *		   10
	 *	     5           12
	 *	  4     7
	 *	       6	
	 */
	BSTreeNode * nodes = (BSTreeNode *)malloc(sizeof(BSTreeNode)*6);
	nodes[0].value = 10;
	nodes[1].value = 5;
	nodes[2].value = 12;
	nodes[3].value = 4;
	nodes[4].value = 7;
	nodes[5].value = 6;

	nodes[0].left = &nodes[1];
	nodes[0].right = &nodes[2];
	nodes[1].left = &nodes[3];
	nodes[1].right = &nodes[4];
	nodes[4].left = &nodes[5];
	

	pair<int,int> ret = max_distance(&nodes[0]);
	printf("The max distance is: %d\n", ret.second);
	free(nodes);
	return 0;
}
